package hashTable;

import java.util.Scanner;

/**
 * @author： pang-yun
 * @date： 2021-10-13 09:37
 * 功能目的 ：用于  使用 散列表 存放 雇员数据 实现快速查找
 */

public class HashTableDemo {


    public static void main(String[] args) {
        // 创建哈希表
        HashTable hashTable = new HashTable(7);

        // 写一个简单菜单
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add: 添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找雇员");

            System.out.println("exit: 退出");

            key = scanner.next();

            switch (key) {
                case "add":
                    System.out.println("id: ");
                    int id = scanner.nextInt();
                    System.out.println("name: ");
                    String name = scanner.next();
                    //创建雇员
                    Employee employee = new Employee(id, name);
                    hashTable.add(employee);
                    break;

                case "find":
                    System.out.println("输入要查找的id");
                    int findId = scanner.nextInt();
                    hashTable.findEmpById(findId);
                    break;
                case "list":
                    hashTable.list();
                    break;

                case "exit":
                    scanner.close();
                    System.exit(0);

                default:
                    break;
            }
        }
    }


    // 创建 HashTable 管理多条链表
    static class HashTable {
        private EmpLinkedList[] empLinkedLists;
        private int size;

        public HashTable(int size) {
            this.size = size;
            empLinkedLists = new EmpLinkedList[size];
            //------------------? 有一个坑-------------记住 每条链表 必须初始化
            for (int i = 0; i < size; i++) {
                empLinkedLists[i] = new EmpLinkedList();
            }
        }

        // 添加雇员
        public void add(Employee emp) {
            // 根据员工的id 得到该员工应当添加到那条链表？
            int num = hashFunc(emp.id);
            empLinkedLists[num].add(emp);
        }

        //遍历所有的链表  遍历hashtable
        public void list() {
            for (int i = 0; i < size; i++) {
                empLinkedLists[i].list(i);
            }
        }

        // 根据 输入的id  查找雇员
        public void findEmpById(int id) {
            // 首先使用散列函数 确定到哪条链表上查找
            int listNo = hashFunc(id);
            Employee employee = empLinkedLists[listNo].findById(id);
            if (employee != null) {
                System.out.printf("在第%d条链表中找到雇员 id= %d\n", listNo + 1, id);
            } else {
                System.out.println("未找到雇员！");
            }
        }

        // 编写一个散列函数  使用一个简单的取模法
        public int hashFunc(int id) {
            return id % size;
        }
    }


    // 表示一个雇员
    static class Employee {
        public int id;
        public String name;
        public Employee next;

        //构造器
        public Employee(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }

    //创建EmpLinkedList  表示链表
    static class EmpLinkedList {
        //头指针  执行第一个Emp
        private Employee head;  //  默认是null

        // 添加雇员到链表
        public void add(Employee emp) {
            if (head == null) {
                head = emp;
                return;
            }

            //如果不是第一个雇员 则使用一个辅助指针
            Employee curEmp = head;
            while (true) {
                if (curEmp.next == null) break;
                curEmp = curEmp.next;
            }
            curEmp.next = emp;
        }


        // 遍历雇员的列表信息
        public void list(int no) {
            if (head == null) {
                System.out.println("第" + no + "条链表为空！");
                return;
            }
            System.out.println("第" + no + "条链表信息为: ");

            // 先创建一个辅助指针
            Employee curEmp = head;

            while (true) {
                System.out.printf("==> id=%d   name=%s\n", curEmp.id, curEmp.name);

                if (curEmp.next == null) break;
                curEmp = curEmp.next;
            }
        }

        // 根据id 查找雇员
        // 如果查找到 就返回 emp  如果没有就返回null
        public Employee findById(int id) {
            if (head == null) {
                System.out.println("链表为空");
                return null;
            }

            //辅助指针
            Employee curEmp = head;
            while (true) {
                if (curEmp.id == id) {
                    break;
                }
                if (curEmp.next == null) {
                    curEmp = null;
                    break;
                }
                curEmp = curEmp.next;
            }
            return curEmp;
        }
    }
}
